package com.linyaonan.leetcode.medium._1679;

import java.util.Arrays;

/**
 *
 * 给你一个整数数组 nums 和一个整数 k 。
 *
 * 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
 *
 * 返回你可以对数组执行的最大操作数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4], k = 5
 * 输出：2
 * 解释：开始时 nums = [1,2,3,4]：
 * - 移出 1 和 4 ，之后 nums = [2,3]
 * - 移出 2 和 3 ，之后 nums = []
 * 不再有和为 5 的数对，因此最多执行 2 次操作。
 * 示例 2：
 *
 * 输入：nums = [3,1,3,4,3], k = 6
 * 输出：1
 * 解释：开始时 nums = [3,1,3,4,3]：
 * - 移出前两个 3 ，之后nums = [1,4,3]
 * 不再有和为 6 的数对，因此最多执行 1 次操作。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^9
 * 1 <= k <= 10^9
 *
 * @author: Lin
 * @date: 2024/3/20
 */
public class MaxNumberOfKSumPairs {

    /**
     * 双指针解法
     * 首先将数组升序排序
     * 然后双指针匹配，
     *  1. 如果 l + r的数值相等对数+1
     *  2. 如果大于目标值r--
     *  3. 如果小于目标值l++
     * @param nums
     * @param k
     * @return
     */
    public int maxOperations(int[] nums, int k) {
        int rCount = 0;
        // 1. 先排序
        Arrays.sort(nums);
        int l = 0;
        int r = nums.length - 1;

        while (l < r) {
            // 需要考虑int溢出
            long add = nums[l] + nums[r];
            // 表示找到
            if (add == k) {
                rCount++;
                l++;
                r--;
            } else {
                if (add > k) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return rCount;
    }

}
